package algorithm;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by lxue on 16/5/4.
 *
 * @email xuelei@aceor.org
 */
public class BankerAlgorithm {
    @Test
    public void testResourceRequest() {
        int[][] allocationVector = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
        int[][] needVector = {{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};
        int[] availableArray = {3, 3, 2};
        //success
        int[] request = {1, 0, 2};
        int requestIndex = 1;
        //fail
//        int[] request = {3, 3, 0};
//        int requestIndex = 4;
        Assert.assertTrue(resourceRequest(allocationVector, needVector, availableArray, request, requestIndex));
        Assert.assertArrayEquals(new int[]{3, 0, 2}, allocationVector[requestIndex]);
    }

    @Test
    public void testCheckWithSafeAlgorithm() {
        int[][] allocationVector = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
        int[][] needVector = {{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};
        int[] availableArray = {3, 3, 2};
        Assert.assertTrue(checkWithSafeAlgorithm(allocationVector, needVector, availableArray));
    }

    public static void main(String[] args) {
        if (args.length != 2) {
            System.out.println("usage :java algorithm.BankerAlgorithmm <pNum> <rNum> " +
                    "\n\t<pNum> : the number of process " +
                    "\n\t<rNum> : the number of resource");
            return;
        }
        try {
            Integer pNum = Integer.valueOf(args[0]);
            Integer rNum = Integer.valueOf(args[1]);
            int[][] allocationVector = new int[pNum][rNum];
            int[][] maxVector = new int[pNum][rNum];
            int[][] needVector = new int[pNum][rNum];
            int[] availableArray = new int[rNum];
            initScanner(allocationVector, maxVector, needVector, availableArray, pNum, rNum);
            testResourceRequest(allocationVector, needVector, availableArray, pNum, rNum);
        } catch (NumberFormatException e) {
            //
            System.out.printf("option parameter error, type must be Integer! <pNum> : %s, <rNum> :  %s", args[0], args[1]);
        }

    }

    private static void testResourceRequest(int[][] allocationVector, int[][] needVector, int[] availableArray, Integer pNum, Integer rNum) {
        int[] request = new int[rNum];
        int requestIndex = -1;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("--------请输入进程编号,进程资源申请向量--------");
            requestIndex = scanner.nextInt();
            for (int j = 0; j < rNum; j++) {
                request[j] = scanner.nextInt();
            }
            resourceRequest(allocationVector, needVector, availableArray, request, requestIndex);
        }
    }

    private static void initScanner(int[][] allocationVector, int[][] maxVector, int[][] needVector, int[] availableArray, int pNum, int rNum) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入进程已分配资源表:");
        for (int i = 0; i < pNum; i++) {
            for (int j = 0; j < rNum; j++) {
                allocationVector[i][j] = scanner.nextInt();
            }
        }
        System.out.println("请输入进程资源最大需求表:");
        for (int i = 0; i < pNum; i++) {
            for (int j = 0; j < rNum; j++) {
                maxVector[i][j] = scanner.nextInt();
                needVector[i][j] = maxVector[i][j] - allocationVector[i][j];
                if (0 > needVector[i][j]) {
                    throw new IllegalArgumentException("进程已分配资源数大于最大需求数");
                }
            }
        }
        System.out.println("请输入资源可利用向量:");
        for (int j = 0; j < rNum; j++) {
            availableArray[j] = scanner.nextInt();
        }
    }

    /**
     * 资源请求
     *
     * @param allocationVector
     * @param needVector
     * @param availableArray
     * @param request
     * @param requestIndex
     * @return true:资源申请成功,false:失败
     */
    public static boolean resourceRequest(int[][] allocationVector,
                                          int[][] needVector,
                                          int[] availableArray,
                                          int[] request,
                                          int requestIndex) {
        System.out.println("资源分配开始");
        //参数校验
        checkResouceRequestParamWithThrowException(allocationVector, needVector, availableArray, request, requestIndex);
        //提前分配资源
        doResourceRequestAllocate(allocationVector, needVector, availableArray, request, requestIndex);
        //安全算法校验
        if (checkWithSafeAlgorithm(
                allocationVector,
                needVector,
                availableArray)) {
            System.out.println("资源分配成功");
            return true;
        } else {
            //校验失败,则不允许资源分配,资源分配回滚
            doResourceRequestAllocateRollback(allocationVector, needVector, availableArray, request, requestIndex);
            System.out.println("资源分配失败");
            return false;
        }
    }

    private static void checkResouceRequestParamWithThrowException(int[][] allocationVector,
                                                                   int[][] needVector,
                                                                   int[] availableArray,
                                                                   int[] request,
                                                                   int requestIndex) {
        //长度边界校验
        if (!(allocationVector.length == needVector.length
                && needVector.length > 0)
                || !(allocationVector[0].length == needVector[0].length
                && needVector[0].length == availableArray.length && availableArray.length == request.length)
                || allocationVector.length <= requestIndex) {
            throw new IllegalArgumentException("参数长度边界错误");
        }
        //请求资源是否超出需求
        for (int i = 0; i < request.length; i++) {
            if (request[i] > needVector[requestIndex][i]) {
                throw new RuntimeException("请求资源超过需求" +
                        ", need :" + Arrays.toString(needVector[requestIndex]) +
                        ", request :" + Arrays.toString(request));
            }
        }
        //请求资源是否超出可分配资源
        for (int i = 0; i < request.length; i++) {
            if (request[i] > availableArray[i]) {
                throw new RuntimeException("请求资源超过需求" +
                        ", available :" + Arrays.toString(availableArray) +
                        ", request :" + Arrays.toString(request));
            }
        }
    }

    private static void doResourceRequestAllocate(int[][] allocationVector,
                                                  int[][] needVector,
                                                  int[] availableArray,
                                                  int[] request,
                                                  int requestIndex) {
        doResourceRequestHandle(allocationVector, needVector, availableArray, request, requestIndex, false);
    }

    private static void doResourceRequestAllocateRollback(int[][] allocationVector,
                                                          int[][] needVector,
                                                          int[] availableArray,
                                                          int[] request,
                                                          int requestIndex) {
        doResourceRequestHandle(allocationVector, needVector, availableArray, request, requestIndex, true);
    }

    private static void doResourceRequestHandle(int[][] allocationVector,
                                                int[][] needVector,
                                                int[] availableArray,
                                                int[] request,
                                                int requestIndex,
                                                boolean rollback) {
        int len = request.length;
        if (rollback) {
            for (int i = 0; i < len; i++) {
                allocationVector[requestIndex][i] -= request[i];
                needVector[requestIndex][i] += request[i];
                availableArray[i] += request[i];
            }
        } else {
            for (int i = 0; i < len; i++) {
                allocationVector[requestIndex][i] += request[i];
                needVector[requestIndex][i] -= request[i];
                availableArray[i] -= request[i];
            }
        }
    }

    /**
     * 安全算法
     *
     * @param allocationVector 已分配
     * @param needVector       需求
     * @param availableArray   可用资源
     * @return
     */
    private static boolean checkWithSafeAlgorithm(
            int[][] allocationVector,
            int[][] needVector,
            int[] availableArray) {
        System.out.println("安全算法检验开始");
        checkSafeAlgorithmParamWithThrowingExcetion(allocationVector, needVector, availableArray);
        int len = allocationVector.length;
        boolean[] finished = new boolean[len];
        //第一层控制轮数
        for (int i = 0; i < len; i++) {
            //第二层控制每个进程处理
            boolean isFind = false;
            for (int j = 0; j < len; j++) {
                if (!finished[j]
                        && canAllocate(needVector[j], availableArray)) {
                    //标记已分配
                    finished[j] = true;
                    //资源回收
                    accumulateAllocation2Available(allocationVector[j], availableArray);
                    //标记本轮扫描找到可分配进程
                    isFind = true;
                    System.out.println("find 进程[" + j + "]," +
                            "allocation: " + Arrays.toString(allocationVector[j]) +
                            ", need: " + Arrays.toString(needVector[j]) +
                            ", available :" + Arrays.toString(availableArray));
                    break;
                }
            }
            if (!isFind) {
                //一轮回没找到则说明处于不安全状态
                System.out.println("安全算法检验不通过");
                return false;
            }
        }
        System.out.println("安全算法检验通过");
        return true;
    }

    private static void checkSafeAlgorithmParamWithThrowingExcetion(int[][] allocationVector, int[][] needVector, int[] availableArray) {
        if (!(allocationVector.length == needVector.length
                && needVector.length > 0)
                || !(allocationVector[0].length == needVector[0].length
                && needVector[0].length == availableArray.length)) {
            throw new IllegalArgumentException("参数长度错误");
        }
    }

    /**
     * 已分配资源回收
     *
     * @param allocationArray
     * @param availableArray
     * @return
     */
    private static void accumulateAllocation2Available(int[] allocationArray, int[] availableArray) {
        for (int i = 0; i < availableArray.length; i++) {
            availableArray[i] += allocationArray[i];
        }
    }

    /**
     * 判断是否可以分配资源
     *
     * @param needArray
     * @param availableArray
     * @return
     */
    private static boolean canAllocate(int[] needArray, int[] availableArray) {
        int len = needArray.length;
        for (int i = 0; i < len; i++) {
            if (needArray[i] > availableArray[i]) {
                return false;
            }
        }
        return true;
    }
}
